package pers.qianyu.month_202011.date_20201130;

import java.util.*;

/**
 * [Leetcode 每日一题]
 * 767. 重构字符串
 * https://leetcode-cn.com/problems/reorganize-string/
 *
 * @author mizzle rain
 * @date 2020-11-30 13:14
 */
public class ReorganizeString2 {
    /**
     * 使用计数
     */
    public String reorganizeString(String S) {
        if (S == null || S.length() < 2) {
            return S;
        }
        int[] map = new int[26];
        for (int i = 0; i < S.length(); i++) {
            map[S.charAt(i) - 'a']++;
        }
        // 如果说有一个字符的数量大于 (n + 1) / 2 的话，就直接返回 ""
        int count = (S.length() + 1) >> 1;
        for (int i = 0; i < 26; i++) {
            if (map[i] > count) {
                return "";
            }
        }
        char[] arr = new char[S.length()];
        int evenIndex = 0, oddIndex = 1;
        for (int i = 0; i < 26; i++) {
            char c = (char) (i + 'a');
            // map[i] <= (S.length() >> 1) 表示如果字符出现的次数大于总数的一半的时候，即等于 (n / 2) + 1 的时候就先放奇数索引
            while (map[i] > 0 && oddIndex < S.length() && map[i] <= (S.length() >> 1)) {
                arr[oddIndex] = c;
                map[i]--;
                oddIndex += 2;
                System.out.println(Arrays.toString(arr));
            }
            while (map[i] > 0) {
                arr[evenIndex] = c;
                map[i]--;
                evenIndex += 2;
                System.out.println(Arrays.toString(arr));
            }
        }
        return new String(arr);
    }


    public static void main(String[] args) {
        String result = new ReorganizeString2().reorganizeString("aab");
        System.out.println("result = " + result);
    }
}
